package io.adrainty.algorithm.leetcode.lcr;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>LCR017. 最小覆盖子串</p>
 * <a href="https://leetcode.cn/problems/M1oyTv/">...</a>
 * @author AdRainty
 * @version V1.0.0
 * @description 最小覆盖子串
 * @since 2025/7/28 13:31:48
 */
public class LCR017 {

    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        if (s.contains(t)) return t;

        // 字典记录t中每个字符出现的次数
        Map<Character, Integer> tMap = getCharacterCntMap(t);

        int left = 0;
        int right = -1;
        int minSize = Integer.MAX_VALUE;
        Map<Character, Integer> window = new HashMap<>();

        int ansL = -1;
        int ansR = -1;
        while (right < s.length()) {
            right++;
            // 窗口中添加一个字符
            if (right < s.length() && tMap.containsKey(s.charAt(right))) {
                window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
            }

            while (check(tMap, window) && left <= right) {
                if (right - left + 1 < minSize) {
                    minSize = right - left + 1;
                    ansL = left;
                    ansR = left + minSize;
                }

                // 缩小窗口
                if (tMap.containsKey(s.charAt(left))) {
                    window.put(s.charAt(left), window.getOrDefault(s.charAt(left), 0) - 1);
                }
                left++;
            }
        }

        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    private static Map<Character, Integer> getCharacterCntMap(String t) {
        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        return tMap;
    }

    private boolean check(Map<Character, Integer> tMap, Map<Character, Integer> window) {
        for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
            if (!window.containsKey(entry.getKey()) || window.get(entry.getKey()) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        LCR017 lcr017 = new LCR017();
        System.out.println(lcr017.minWindow("bbaac", "aba"));
    }

}
